package sort;

import java.awt.font.NumericShaper;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Stack;

public class Sort {
    //实现插入排序
    //把整个数组划分成有序区间和无序区间
    //每次取出无序区间的第一个元素,插入到有序区间中合适的位置
    //整个过程循环N-1次
    public static void insertSort(int[] arr){
        //bound变量表示边界
        //[0,bound)区间是有序区间
        //[bound,arr.length)区间是无序区间
        for(int bound = 1;bound < arr.length;bound++){
            int value = arr[bound];
            //value就是无序区间的第一个元素
            //拿着整个元素,在有序区间中,从后往前进行比较
            int cur = bound - 1;
            for(;cur >= 0;cur--){
                if(arr[cur] > value){
                    //没有写等于的情况,相当于等于时什么都不做,直接将value放在cur后,这样就保持的稳定性
                    arr[cur + 1] = arr[cur];
                }else{
                    break;
                }
            }
            //意味着value就应放到cur之后,也就是cur+1的位置
            arr[cur + 1] = value;
        }
    }

    //分组进行插入排序
    //根据gap值把整个数组分成多个组,针对每个组进行插入排序
    //此处使用希尔排序,gap为size/2,size/4,size/8.....1
    private static void shellSort(int [] arr){
        int gap = arr.length / 2;
        while(gap >= 1){
            //针对每个组进行插入排序
            insertSortGap(arr,gap);
            System.out.print("gap = " + gap + ":");
            System.out.println(Arrays.toString(arr));
            gap /= 2;

        }
    }

    //分组插入排序
    private static void insertSortGap(int []arr,int gap){
        //针对每个组进行插入排序
        //此处,同一个内部元素下标的差值为gap,一个元素的下个元素的下标是,bound += gap
        //但是此处的处理其实是针对所有的组同时来处理
        //例如gap的值为3,bound在循环的过程中,就是在处理第0组第一个元素的插入,再处理第一组,第二组第一个元素的插入
        //接着再依次处理第0组,第1组,第2组的第二个元素的插入
        for(int bound = gap;bound < arr.length;bound++){
            //value表示待插入的元素
            int value = arr[bound];
            //利用cur作为下标来取出value所在组的第一个元素(下标差值是gap)
            int cur = bound - gap;
            for(;cur >= 0;cur -= gap){
                if(arr[cur] > value){
                    //需要搬运
                    arr[cur + gap] = arr[cur];
                    //执行了这一步的话,还会跳上去,cur就会继续减去gap
                }else{
                    //如果满足顺序,就不用比较了,直接跳出循环,开始下一轮
                    //相当于cur还是bound - gap
                    //后面arr[cur + gap] = value;
                    //还是arr[bound] = gap
                    break;
                }
            }
            //找到了插入的位置,进行插入
            //认为value插入到cur之后,也就是cur + gap的位置
            arr[cur + gap] = value;

        }
    }





    //选择排序
    public static void selectSort(int [] arr){
        //当bound达到length - 1的位置时,整个数组就排序完成了
        //外层的bound可以看作是有序区间的下标,内层循环的cur可以看作是无序区间的下标
        for(int bound = 0;bound < arr.length - 1;bound++){
            //采用打擂台赛的方式进行比较
            for(int cur = bound + 1;cur < arr.length;cur++){
                if(arr[cur] < arr[bound]){
                    int temp = arr[cur];
                    arr[cur] = arr[bound];
                    arr[bound] = temp;
                }
            }
            System.out.println("bound" + bound + ":" + Arrays.toString(arr));
        }
    }

    //堆排序核心思想,建大堆,升序
    //把堆顶元素和最后一个元素交换,再重新向下调整
    public static void heapSort(int[] arr){
        //1,建堆
        createHeap(arr);
        //2,依次把堆顶元素和待排序区间的最后一个元素进行交换
        //此处设定[0,bound]区间为待排序区间
        int bound = arr.length - 1;
        for(int i = 0;i < arr.length - 1;i++){
            int temp = arr[0];
            arr[0] = arr[bound];
            arr[bound] = temp;
            shiftDown(arr,bound,0);
            //重新调整堆
            //通过bound表示堆中元素的个数
            //把最后一个元素归入到已排序区间
            bound--;
        }
    }

    //把堆从index位置开始向下调整
    //length表示堆中元素的个数
    private static void shiftDown(int[] arr, int length, int index) {
        int parent = index;
        int child = 2 * parent + 1;
        while(child < length){
            if(child + 1 < length&&arr[child] < arr[child + 1]){
                child += 1;
            }
            if(arr[parent] < arr[child]){
                int temp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = temp;
                parent = child;
                child = 2 * parent + 1;
            }else{
                break;
            }
        }
    }


    private static void createHeap(int [] arr) {
        for(int i = (arr.length - 1 - 1)/2;i >= 0;i--){
            shiftDown(arr,arr.length,i);
        }
    }

    //冒泡排序
    //比较两个相邻元素,不符合升序要求,就交换
    //此处按照从后往前的方式进行遍历,每次都能把最小值放在前面
    //此时可以约定[0,bound)为已排序区间,[bound,arr.length)为待排序区间
    public static void bubbleSort(int [] arr){
        //通过bound确定好循环次数
        for(int bound = 0;bound < arr.length - 1;bound++){
            //注意边界,初始值为arr.length - 1,就意味着下面的if是cur和cur - 1的比较
            //另外,cur > bound不用写作大于等于,因为bound前面的元素都是有序的
            //就不需要再比较arr[length - 1]了
            for(int cur = arr.length - 1;cur > bound;cur--){
                if(arr[cur - 1] > arr[cur]){
                    int temp = arr[cur - 1];
                    arr[cur - 1] = arr[cur];
                    arr[cur] = temp;
                }
            }
        }
    }

    //快速排序，总的入口
    public static void quickSort(int [] arr){
        quickSort(arr,0,arr.length - 1);
    }

    //快速排序，辅助递归的方法。
    //此处约定[left,right]为待排序的区间
    //约定成前闭后开区间也是可以的，但是代码会稍微复杂一些

    public static void quickSort(int [] arr,int left,int right){
        if(left >= right){
            //待处理区间为空，或者只有一个元素，无需排序
            return;
        }
        //针对区间进行整理，返回值index 表示基准值所在的下标位置，明确了基准值的位置，才能进一步的针对他的最优区间，进行递归
        int index = partition(arr,left,right);//这个函数相当于即进行一些列交换操作，也返回值
        //递归左半区间
        quickSort(arr,left,index - 1);
        //递归右半区间
        quickSort(arr,index + 1,right);
        //这里的区间都是闭区间，就特别清楚，隔断成了三个部分。

    }

    public static int partition(int [] arr,int left,int right){
        //如果是自己写的代码，就不用double check了，因为自己已经知道前面那里已经检查过左右区间是否为空或只有一个元素
        //1,设定最右侧元素作为基准值
        int value = arr[right];
        //2，设定两个下标，分别从左往右和从右往左进行搜索
        int l = left;
        int r = right;
        while(l < r){
            //先从左往右，找比基准值大的元素
            while(l < r && arr[l] <= value){
                l++;
            }
            while(l < r && arr[r] >= value){
                r--;
            }
            //因为可能有多个符合，也可能只有一个符合，因此外层循环要写开
            //如此以来，l就停到了从左往右比基准值大的元素上，r就停到了从右往左比基准值小的元素上。
            //这里就算l和r重合了，也可以用swap,自己和自己交换，没什么问题。
            swap(arr,l,r);
        }
        swap(arr,l,right);
        //最后把基准值换到中间，这样基准值的左边比它小，右边比它大
        return l;
        //返回l的位置，作为基准值位置。
    }
    private static void swap(int [] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    //[left,right]为待处理区间
    static class Range{
        public int left;
        public int right;

        public Range(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }

    public static void quickSortByLoop(int [] arr){
        Stack<Range> stack = new Stack<>();
        //初始情况下，把整个数组的区间加入到栈中
        stack.push(new Range(0,arr.length - 1));
        while(!stack.isEmpty()){
            //弹出栈顶的区间
            Range range = stack.pop();
            if(range.left >= range.right){
                //区间为空，或者只有一个元素，不需要排序
                continue;
            }
            //区间不为空，使用partition进行整理
            int index = partition(arr,range.left,range.right);
            //把左侧区间和右侧区间入栈，下次循环出栈，取出的当前这样的子区间
            stack.push(new Range(range.left,index - 1));
            stack.push(new Range(index + 1,range.right));
        }
        //整个栈顺序为空了，说明排序完毕了
    }

    //归并排序的入口方法
    public static void mergeSort(int[] arr){
        mergeSort(arr,0,arr.length - 1);
    }

    //归并排序的辅助方法，参数中引入子区间，通过子区间来决定当前是要针对哪个部分的数组来进行归并排序
    //约定[left,right]闭区间为待处理区间
    private static void mergeSort(int []arr,int left,int right){
        //如果子区间中没有元素，或者只有一个元素，就不需要继续递归
        if(left >= right){
            return;
        }
        //2,把当前区间分成两个等长的区间，分别进行递归
        //   此处计算min的时候，加不加1都行
        int mid = (left + right) / 2;
        //3，递归左半区间，递归右半区间
        //      快速排序，是分成3个部分，基准值是单独的一部分，左右递归的时候，需要把基准值的位置排除的
        //      归并排序，是分成两个部分，mid这个位置的元素，也是要参与递归的
        mergeSort(arr,left,mid);
        mergeSort(arr,mid + 1,right);
        //上述递归完成以后，说明左右两个区间，已经是有序的了，接下来针对这两个区间进行合并即可
        merge(arr,left,mid,right);
    }


    //此时相当于左侧区间[left,mid]和右侧区间[mid + 1,right]已经是有序的了
    //把这两个区间进行合并，合并之后，把最终结果放在[left，right]区间中

    private static void merge(int [] arr,int left,int mid,int right){
        //由于调用这个方法前已经判定过区间有效了，也就不需要进行边界判定了
//        if(left >= right){
//            return;
//        }
        //先创建一个临时数组，保存合并的结果，临时数组的长度应该是right - left + 1
        int [] result = new int[right - left + 1];
        //后续合并的时候，须把对应的元素尾插到result中，找到resultSize表示result中已经插入的元素的个数
        //此处就是模拟简单的顺序表
        int resultSize = 0;

        //2,设置两个下标指向每个区间的开头位置
        int cur1 = left;
        int cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= right){
            if(arr[cur1] <= arr[cur2]){
                //这里写作<=可以保证稳定性，当两个数大小相等时，先把前面的数插入到数组中
                //把cur1位置的元素尾插到result中
                result[resultSize++] = arr[cur1];
                cur1++;
            }else{
                //把cur2位置的元素尾插到result中
                result[resultSize++] = arr[cur2];
                cur2++;
            }
        }
        //3，处理剩余的元素，由于这两个区间的长度不一定完全相等，只需要把多余的部分，整体尾插到result中即可
        while(cur1 <= mid){
            result[resultSize++] = arr[cur1++];
        }
        while(cur2 <= right){
            result[resultSize++] = arr[cur2++];
        }
        //4，把result临时数组中的结果，写回到arr的[left,right]区间中
        for(int i = 0;i < result.length;i++){
            arr[left + i] = result[i];
        }
    }

    //非递归版本的归并排序，本质是就是把长度为1的两两合并，再把长度为2的两两合并，再把长度为4的两两合并
    //完全可以跳过递归，直接按照上述次序进行合并即可
    private static void mergeSortByLoop(int [] arr){
        //创建一个变量，表示当前要合并的数组的大小
        for(int size = 1;size < arr.length;size *= 2){
            //在循环内部，进行两两合并
            for(int i = 0;i < arr.length;i += size * 2){
                //这个循环的意思就是，一般是合并两个长度为size的数组，进行合并，再取两个长度为size的数组，再合并
                //依次类推，直到把整个数组都循环完
                //每次循环，i就对应着两个数组
                //这俩数组的区间是[i,i + size - 1]和[i + size,i + size * 2 - 1]
                //有时合并时没有相邻数组
                int left = i;
                int mid = i + size - 1;
                if(mid >= arr.length - 1){
                    mid = arr.length - 1;
                }
                int right = i + size * 2 - 1;
                if(right >= arr.length - 1){
                    right = arr.length - 1;
                }
                merge(arr,left,mid,right);
            }
        }
    }

    public static void main(String[] args) {
        int[]arr = {9,5,2,7,3,6};
//        insertSort(arr);
//        shellSort(arr);
//        selectSort(arr);
//        heapSort(arr);
//        bubbleSort(arr);
//        quickSort(arr);
//        quickSortByLoop(arr);
//        mergeSort(arr);
//        mergeSortByLoop(arr);
        System.out.println(Arrays.toString(arr));
    }
}
